package com.captain.special.链表;

import com.captain.leetcode.链表.ListNode;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Des:
 *
 * @author XL
 * @Date 2022/4/1 9:01
 */
public class 从链表中删去总和值为零的连续节点1171 {
    public static void main(String[] args) {
        new 从链表中删去总和值为零的连续节点1171().removeZeroSumSublists(ListNode.getInstance());
    }

    public ListNode removeZeroSumSublists(ListNode head) {
        if (head == null) return null;
        // 0 -3 1 -2 1 4 5
        // 0 -3-2 -4-3 1 6
        ListNode dummy = new ListNode(0, head);
        Map<Integer, ListNode> map = new HashMap<>(16);
        ListNode cur = dummy;
        int sum = 0;
        while (cur != null) {
            int value = cur.val;
            sum += value;
            map.put(sum, cur);
            cur = cur.next;
        }
        sum = 0;
        cur = dummy;
        // 0  1 2 -3 3 1
        while (cur != null) {
            sum += cur.val;
            cur.next = map.get(sum).next;
            cur = cur.next;
        }
        return dummy.next;
    }
}
